#include<stdio.h>
#include<algorithm> 
using namespace std;
const int maxn=100;
int main()
{
	int n,m;
	int x[maxn],y[maxn];
	int dp[maxn][maxn];
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	printf("\n");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j-x[i]<0)  
				dp[i][j]=dp[i-1][j];
			else  
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-x[i]]+y[i]);
			printf("%3d ",dp[i][j]);
		}
		printf("\n");
	}
	printf("\n%d",dp[n][m]);
	return 0;
}

